/**
 * 冒泡排序
 * 相邻两个对比，最后把最大的排到了最后，重复此过程
 * @param {*} arr 
 * @returns 
 */
function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {        //相邻元素两两对比
        var temp = arr[j + 1];        //元素交换
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

/**
 * 选择排序
 * 寻找最小的数，保存索引，然后与第一层循环其下标对于的值进行交换
 * @param {*} arr 
 * @returns 
 */
function selectionSort(arr) {
  var len = arr.length;
  var minIndex, temp;
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {     //寻找最小的数
        minIndex = j;                 //将最小数的索引保存
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

/**
 * 快速排序
 * 选取一个记录作为中间轴，然后将比‘这个记录值’小的移到‘记录值’之前，大的移到之后，然后递归
 * @param {*} arr 
 * @returns 
 */
function quickSort(arr) {
  if (arr.length == 0) {
    return [];    // 返回空数组
  }
  var cIndex = Math.floor(arr.length / 2);
  var c = arr.splice(cIndex, 1);
  var l = [];
  var r = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < c) {
      l.push(arr[i]);
    } else {
      r.push(arr[i]);
    }
  }
  return quickSort(l).concat(c, quickSort(r));
}

/**
 * 双指针快排
 * @param {*} arr 
 * @param {*} begin 
 * @param {*} end 
 * @returns 
 */
function quickSort(arr, begin, end) {
  if (begin >= end) {
    return
  }
  let temp = arr[begin];
  let left = begin;
  let right = end;
  while (right > left) {
    while (right > left && arr[right] >= temp) {
      right--;
    }
    while (right > left && arr[left] <= temp) {
      left++;
    }
    [arr[left], arr[right]] = [arr[right], arr[left]];
  }

  [arr[begin], arr[right]] = [arr[right], arr[begin]];
  quickSort(arr, begin, right - 1);
  quickSort(arr, right + 1, end);
  return arr;
}

const arr = [3, 6, 1, 2, 5, 4];
const result = quickSort(arr, 0, arr.length - 1);
console.log(result);

/**
 * 调整数组顺序使奇数位于偶数前面(借助新数组)
 * @param {*} nums 
 * @returns 
 */
var exchange = function (nums) {
  let newArr = []
  nums.forEach(function (value, index) {
    if (value % 2 !== 0) {
      newArr.unshift(value)
    } else {
      newArr.push(value)
    }
  })
  return newArr
};
/**
 * 调整数组顺序使奇数位于偶数前面(首尾双指针)
 * @param {*} nums 
 * @returns 
 */
var exchange = function (nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    // 首指针，找出偶数
    while (left <= right && nums[left] % 2 !== 0) {
      left++
    }
    // 尾指针，找出奇数
    while (left <= right && nums[right] % 2 === 0) {
      right--
    }
    if (left > right) {
      break
    }
    [nums[left], nums[right]] = [nums[right], nums[left]]
    left++;
    right--;
  }
  return nums
};

/**
 * reduce
 * @param {*} callback 
 * @param  {...any} args 
 * @returns 
 */
Array.prototype.sx_reduce = function (callback, ...args) {
  let start = 0, pre
  if (args.length) {
    pre = args[0]
  } else {
    pre = this[0]
    start = 1
  }
  for (let i = start; i < this.length; i++) {
    pre = callback(pre, this[i], i, this)
  }
  return pre
}